package com.leecode.exercise;

/**
 * @Author: shubin_yao
 * @Date: 2022/06/16/12:49
 * @Description: 跳跳游戏
 */
public class JumpSolution {
    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        Solution3 solution3 = new Solution3();
        System.out.println(solution3.jump(nums));
    }
}

class Solution3 {

    public int jump(int[] nums) {
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for(int i = 0; i < nums.length -1; i++){
            //找能跳的最远的
            maxPosition = Math.max(maxPosition, nums[i] + i);
            if( i == end){ //遇到边界，就更新边界，并且步数加一
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    //int[] nums = {2, 3, 1, 1, 4};
    //                   !
   /* public int jump(int[] nums) {
        int index = 0;
        int temp = nums[0];
        int count = 0;
        if (nums.length == 0 || nums.length == 1) {
            return 1;
        }
        for (int i = 0; i < nums.length-1; i++) {
            if (temp < (nums.length - 1 - i)) {
                index = index + temp;
                for (int j = i + 1; j < index; j++) {
                    if (nums[j] < (nums.length - 1 - j) && nums[j] > (nums.length - index)) {
                        temp = nums[j];
                        index = j;
                        count ++;
                    }else{
                        temp = nums[index];
                        count ++;
                    }
                }
            }
        }
        return count;
    }*/
}
